package com.swak.algs;

import com.swak.algs.sample.Samples;

/**
 * 归并排序的非递归算法： 递归算法见：@Code15
 * 
 * @author 618lf
 */
public class Code21 {

	static void process(int[] arr) {

		/*
		 * 基本性的判断
		 */
		if (arr == null || arr.length < 2) {
			return;
		}

		/*
		 * 数组的长度
		 */
		int N = arr.length;

		/*
		 * 步长按照2次方来增长
		 */
		int step = 1;
		while (step < N) {

			/*
			 * 从第个数开始按照步长合并
			 */
			int L = 0;

			/*
			 * 必须要满足左边数据足够，且至少有一个右边数
			 */
			while (L < N) {
				int LR = L + step - 1;
				int R = LR + 1;
				int RR = Math.min(R + step - 1, N - 1);
				if (LR >= N || R >= N) {
					break;
				}

				/*
				 * 合并，将一个数组的指定范范围的数据惊醒合并拷贝
				 */
				Code15.merge(arr, L, LR, R, RR);

				/*
				 * 下一组数
				 */
				L = L + (step << 1);
			}

			/*
			 * 防止溢出
			 */
			if (step > N / 2) {
				break;
			}

			/*
			 * 步长按照2次方来增长
			 */
			step = step << 1;
		}
	}

	public static void main(String[] args) {
		Samples.randomSampleTest(10, 10, 100000, (arr) -> {
			process(arr);
		}, (arr) -> {
			Code04.insertSort(arr);
		});
//		System.out.println("=================");
//		int[] arr = { 1, 4, -4, -4 };
//		Prints.print(arr);
//		process(arr);
//		Prints.print(arr);
	}
}